package com.jack.leetcode.eachProblem07;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class 最小区间 {

    private class NumGroup {
        public NumGroup(int num, int grp) {
            this.num = num;
            this.grp = grp;
        }

        int num;
        int grp;
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<NumGroup> numGrp = new PriorityQueue<>(new Comparator<NumGroup>() {
            @Override
            public int compare(NumGroup o1, NumGroup o2) {
                return o1.num - o2.num;
            }
        });

        //每个group的起始位置
        int[] index = new int[nums.size()];
        int end = -1;
        //起始区间
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i).get(0) > end) {
                end = nums.get(i).get(0);
            }
            NumGroup group = new NumGroup(nums.get(i).get(0), i);
            numGrp.offer(group);
        }
        int max = end;
        int start = numGrp.peek().num;
        int min = start;
        int len = end - start + 1;

        while (true) {
            //当前最小元素的组号
            int grp = numGrp.poll().grp;
            if (index[grp] + 1 == nums.get(grp).size()) {
                break;
            }
            index[grp]++;
            NumGroup numGroup = new NumGroup(nums.get(grp).get(index[grp]), grp);
            numGrp.offer(numGroup);
            if (numGroup.num > max) {
                max = numGroup.num;
            }
            min = numGrp.peek().num;
            if (max - min + 1 < len) {
                start = min;
                end = max;
                len = max - min + 1;
            }
        }
        return new int[]{start, end};
    }
}
